#include <iostream>
#include <algorithm>
using namespace std;

class list{
	public:
		struct node{
			node(int d):data(d){}
			int data;
			node* next;
		};
		list():head(NULL){}
		~list(){
			while(head){
				node* p=head;
				delete head;
				head=head->next;
			}
		}
		void inserthead(int d){
			node* p=head;
			head=new node(d);
			head->next=p;
		}
		void insertafter(node*p,int d){
			node* q=p->next;
			p->next=new node(d);
			p->next->next=q;
		}
		void del(node* p){
			if(head ==p){
				head=head->next;
				delete p;
				return;
			}

			node* q=head;
			while(q){ 
				if(q->next == p){
					break;
				}
				q=q->next;
			}
			if(!q)
				return;
			q->next=p->next;
			delete p;
		}
		node* findfirst(int d){
			node* p=head;
			while(p){
				if(p->data == d)
					break;
				p=p->next;
			}
			return p;
		}
		void print(){
			node* p=head;
			while(p){
				cout<<p->data<<" ";
				p=p->next;
			}
			cout<<endl;
		}
	private:
		node* head;
};

int main(int argc, char* argv[]){                                                                            
	int a[]={0,1,2,3,4,5,6,7,8,9};
	list l;
	for(int i=0;i<sizeof(a)/sizeof(int);i++){
		l.inserthead(a[i]);
	}
	cout<<"before delete\n";
	l.print();

	srand(time(NULL));
	int d=rand()%15;

	list::node* p=l.findfirst(d);
	if(p){
		cout<<"found "<<p->data<<endl;
		l.del(p);
	}else{
		cout<<"not found "<<d<<endl;
	}

	cout<<"after delete\n";
	l.print();

	d=rand()%10;
	p=l.findfirst(d);
	if(p){
		cout<<"found "<<p->data<<endl;
		l.insertafter(p,20);
	}else{
		cout<<"not found "<<d<<endl;
	}

	cout<<"after insert 20 after "<<d<<"\n";
	l.print();

	return 0;                                                            
}

